import math

import numpy as np
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
def create_linked_list(arr):#将传入的数组转化为链表
    head = ListNode(arr[0])
    cur = head
    for i in range(1, len(arr)):
        cur.next = ListNode(arr[i])
        cur = cur.next
    return head
def print_linked_list(head):#传入链表头节点，以数组形式返回
    cur = head
    res = []
    while cur:
        res.append(cur.val)
        cur = cur.next
    return res
class Solution(object):
    def twoSum(self, nums, target):#俩数之和
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        x = 0
        y = 0
        for i in range(len(nums)):
            x = i
            for j in range(len(nums)-i):
                y = i+j
                if nums[x]+nums[y] == target and x!=y:
                    return [x,y]
                else:
                    continue
    def isPalindrome(self, x):#回文数
        if x >= 0 and x < 10:
            return True
        if x<=0 or x%10 == 0:
            return False
        else:
            d = 0
            a = x // 10
            b = x % 10
            e= x
            while e!=0:
                e=e//10
                d+=1
            c=0
            while a!=0:
                d-= 1
                c = c + b * (10 ** d)
                b = a % 10
                a = a//10
            if c + b ==x:
                return True
            else:
                return False
    def missingNumber(self, nums:[int]) -> int:#消失的数字
        l = len(nums) + 1
        new = [0] * l
        for i in nums:
            new[i] = 1
        for x in range(l):
            if new[x] == 0:
                print(x)
                return x
                break
    def missingTwo(self, nums:[int]) -> int:#消失的俩个数字
        l = len(nums) + 3
        new = [0] * l
        y =[0]*2
        j = 0
        for i in nums:
            new[i] = 1
        for x in range(l-1):
            if new[x+1] == 0:
                y[j] = x+1
                j+=1
                continue
        return y
    def candy(self, ratings:[int]) -> int: #分发糖果
        num = len(ratings)
        nums = [1] * num
        for i in range(num - 1):
            if ratings[i + 1] > ratings[i]:
                nums[i + 1] = nums[i] + 1
        while num > 1:
            if ratings[num - 2] > ratings[num - 1] and nums[num - 2] <= nums[num - 1]:
                nums[num - 2] = nums[num - 1] + 1
            num -= 1
        return sum(nums)
    def eraseOverlapIntervals(self, intervals: [[int]]) -> int:#无重叠区间
        intervals = sorted(intervals, key=(lambda X: [X[1], X[1] - X[0]]))
        count = 1
        end = intervals[0][1]
        for item in intervals:
            if item[0] >= end:
                end = item[1]
                count += 1
        return len(intervals) - count
    def plusOne(self, digits: [int]) -> [int]:#加一
        x = len(digits)
        s = [9]*x
        if digits == s:
            r = [0]*(x+1)
            r[0] = 1
            return r
        if digits[x-1]<9:
            digits[x-1]+=1
            return digits
        while digits[x-1] == 9:
            digits[x-1] = 0
            x-=1
        digits[x-1]+=1
        return digits
    def searchInsert(self, nums: [int], target: int) -> int:#搜索插入位置,二分查找
        i = 0
        j = len(nums)-1
        while i <= j:
            if nums[(i+j)//2] == target:
                return (i+j)//2
            elif nums[(i+j)//2] > target:
                j = (i+j)//2-1
            elif nums[(i+j)//2] < target:
                i = (i+j)//2+1
        return j+1
    def merge(self, nums1: [int], m: int, nums2: [int], n: int) -> None:#合并俩个有序数组.太复杂啦,想多了
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0:
            for i in range(n):
                nums1[i] = nums2[i]
            return nums1
        t = 0
        for i in range(n):
            nums1.pop(m)
        for i in range(n):
            if nums2[i] < nums1[m - 1 +t]:
                for j in range(m+n):
                    if nums2[i] <= nums1[j]:
                        t += 1
                        nums1.insert(j, nums2[i])  # 先是插入位置然后是数据
                        break
            else:
                t += 1
                nums1.insert(m + t - 1, nums2[i])
                continue
        return nums1
    def removeDuplicates(self, nums: [int]) -> int:#删除有序数组中的重复项
        i = 0
        n = 0
        while i < len(nums) - 1:
            if nums[i] == nums[i + 1]:
                nums.pop(i)
            else:
                i += 1
                n += 1
        return n+1
    def generate(self, numRows: int) -> [[int]]:#杨辉三角
        if numRows == 0:
            return [[]]
        else:
            lb = []
            for i in range(numRows):
                if i == 0:
                    lb.append([1])
                else:
                    temp = [1]*(i+1)
                    for j in range(1, i):
                        temp[j] = lb[i-1][j] + lb[i-1][j-1]
                    lb.append(temp)
            return lb
    def getRow(self, rowIndex: int) -> [int]:#杨辉三角2
        if rowIndex == 0:
            return [1]
        newrow = Solution.getRow(self, rowIndex - 1)
        row = [1] * (rowIndex + 1)
        for i in range(1, rowIndex):
            row[i] = newrow[i] + newrow[i - 1]
        return row
    def firstMissingPositive(self, nums:[int]) -> int:#缺失的第一个正数
        nums.sort()
        m = 1
        for i in range(len(nums)):
            if nums[i] == m:
                m += 1
        return m
    def intersection(self, nums1: [int], nums2: [int]) -> [int]:#俩个数组的交集
        result = []
        for i in nums1:
            if i in nums2 and i not in result:
                result.append(i)
        return result
    def twoSum(self, nums: [int], target: int) -> [int]:#和为s的俩个数字
        '''双指针'''
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] + nums[j] == target:
                return [nums[i], nums[j]]
            elif nums[i] + nums[j] < target:
                i += 1
            else:
                j -= 1
    def lengthOfLastWord(self, s: str) -> int: #最后一个单词的长度
        h = s.split()[-1:]
        n = ''.join(h)
        return len(n)
    def findRepeatNumber(self, nums): #数组中重复的数字
        n = len(nums)
        zeros = [0] * n
        for i in range(n):
            if zeros[nums[i]] == 1:
                return nums[i]
            else:
                zeros[nums[i]]+=1
    def findNumberIn2DArray(self, matrix: [[int]], target: int) -> bool:  # 剑指 Offer 04. 二维数组中的查找
        m = len(matrix)
        if (m == 0):
            return False
        n = len(matrix[0])
        i = 0
        j = n - 1
        while (i < m and j >= 0):
            if (matrix[i][j] == target):
                return True
            elif (matrix[i][j] > target):
                j -= 1
            else:
                i += 1
        return False
    def replaceSpace(self, s: str) -> str:#替换空格
        s = s.replace(' ', '%20')
        return s
    def buildTree(self, preorder: [int], inorder: [int]) -> TreeNode:#剑指 Offer 07. 重建二叉树
        if len(preorder) == 0:
            return None
        if len(preorder) == 0:
            return TreeNode(preorder[0])
        i = inorder.index(preorder[0])

        leftpre = preorder[1:i+1]
        leftin = inorder[0:i]

        rightpre = preorder[i+1:]
        rightin = inorder[i+1:]

        head = TreeNode(preorder[0])
        head.left = self.buildTree(leftpre, leftin)
        head.right = self.buildTree(rightpre, rightin)
        return head
    def fib(self, n: int) -> int:#剑指 Offer 10- I. 斐波那契数列
        MOD = 10 ** 9 + 7
        if n < 2:
            return n
        p, q, r = 0, 0, 1
        for i in range(2, n + 1):
            p = q
            q = r
            r = (p + q) % MOD
        return r
    def numWays(self, n):
        """
        :type n: int
        :rtype: int
        """
        if(n == 0):
            return 1
        if(n < 3):
            return n
        p,q,r = 0, 1, 2
        for i in range(3, n+1):
            p = q
            q = r
            r = (p+q) % (1e9+7)
        return r
    def cuttingRope(self, n: int) -> int:#剑指 Offer 14- I. 剪绳子
        if n <= 3:
            return n - 1
        x = n // 3
        y = n % 3
        if y == 1:
            return 3 ** (x - 1) * 4
        elif y == 0:
            return 3 ** x
        else:
            return 3 ** x * 2
    def cuttingRope2(self, n: int) -> int:#剑指 Offer 14- II. 剪绳子 II
        mod = 1e9 + 7
        if n <= 3:
            return n - 1
        x, y, rep = n // 3 - 1, n % 3, 1
        for i in range(x):
            rep = (rep * 3) % mod
        if y == 1:
            return int((rep * 4) % mod)
        elif y == 0:
            return int((rep * 3) % mod)
        else:
            return int((rep * 6) % mod)
    def hammingWeight(self, n: int) -> int:#剑指 Offer 15. 二进制中1的个数
        ret = sum(1 for i in range(32) if n & (1 << i)) #当检查第ii位时，我们可以让n与2^i进行与运算，当且仅当n的第i位为1时，运算结果不为0
        #==========
        tmp = []
        for i in range(32):
            if n & (1 << i):
                tmp.append(1)
        ret = sum(tmp)
        return ret
        #=======
        # a = 0
        # while n > 0:
        #     a += n % 2
        #     n = n // 2
        # return a
    def myPow(self, x: float, n: int) -> float:#剑指 Offer 16. 数值的整数次方
        #快速幂+递归.
        def quickmul(N):
            if N == 0:
                return 1.0
            y = quickmul(N//2)
            if N % 2 == 1:
                return y*y*x
            else:
                return y*y
        return quickmul(n) if n > 0 else 1.0/quickmul(-n)
        #快速幂 + 迭代
        x_con = x
        m = 1.0
        if (n == 0):
            return 1.0
        y = math.fabs(n)
        while (y != 0):
            if y % 2 == 1:
                m *=x_con
            x_con *=x_con
            y = y//2
        if n > 0:
            return m
        else:
            return 1.0/m
    def maxSubArray(self, nums: [int]) -> int:#剑指 Offer 42. 连续子数组的最大和
        if len(nums) == 1:
            return nums[0]
        dp = [0]*len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], dp[i-1] + nums[i])
        return max(dp)
    def maxValue(self, grid: [[int]]) -> int: #剑指 Offer 47. 礼物的最大价值
        m, n = len(grid), len(grid[0])
        dp = [[0]*n for i in range(m)] #初始化全0矩阵
        dp[0][0] = grid[0][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(grid[i][j]+dp[i][j-1], grid[i][j]+dp[i-1][j])
        return dp[m-1][n-1]
    def minCostClimbingStairs(self, cost: [int]) -> int:#剑指 Offer II 088. 爬楼梯的最少成本
        dp = [0]*len(cost)
        dp[1] = min(cost[0], cost[1])
        if len(cost) > 2:
            dp[2] = min(cost[0]+cost[2], cost[1])
        if len(cost) > 3:
            for i in range(3, len(cost)):
                dp[i] = min(cost[i]+dp[i-1], cost[i-1]+dp[i-2])
        return dp[len(cost)-1]
    def spiralOrder(self, matrix: [[int]]) -> [int]:#剑指 Offer 29. 顺时针打印矩阵
        # return (matrix and list(matrix.pop(0)) + self.spiralOrder(list(zip(*matrix))[::-1]))#厉害矩阵“削头”（取第一行，并去掉第一行）
        # 后旋转90°（将剩下的矩阵转置），再继续“削头”，从而模拟螺旋。
        res = []
        tran = matrix
        while(tran != []):
            for i in range(len(tran[0])):
                res.append((tran[0][i]))
            tran.pop(0)
            tran = list(zip(*tran))[::-1]
        return res
    def firstUniqChar(self, s: str) -> str:#剑指 Offer 50. 第一个只出现一次的字符
        if s == ' ':
            return ' '
        s = list(s)
        for i in range(len(s)):
            try:
                temp = s[i]
                s[i] = ' '
                s.index(temp)
                s[i] = temp
            except:
                return temp
        return ' '
    def getLeastNumbers(self, arr: [int], k: int) -> [int]:#剑指 Offer 40. 最小的k个数
        # arr.sort()
        # return arr[:k]
        res = []
        for i in range(k):
            res.append(min(arr))
            arr.remove(min(arr))
        return res
    def majorityElement(self, nums:[int]) -> int:#剑指 Offer 39. 数组中出现次数超过一半的数字
        n = len(nums)
        num = 0
        temp = nums[0]
        for i in range(n):
            if num == 0:
                temp = nums[i]
            if nums[i] == temp:
                num+=1
            else:
                num-=1
        return temp
    def deleteNode(self, head: ListNode, val: int) -> ListNode:#剑指 Offer 18. 删除链表的节点
        if head.val == val:
            head = head.next
        zan = head
        while(zan.next):
            temp = zan
            temp1 = temp.next
            if temp1.val == val:
                temp.next = temp1.next
            zan = zan.next
            if(not zan):
                break
        return print_linked_list(head)
    def isNumber(self, s: str) -> bool:#剑指 Offer 20. 表示数值的字符串
        states = [
            {' ': 0, 's': 1, 'd': 2, '.': 4},  # 0. start with 'blank'
            {'d': 2, '.': 4},  # 1. 'sign' before 'e'
            {'d': 2, '.': 3, 'e': 5, ' ': 8},  # 2. 'digit' before 'dot'
            {'d': 3, 'e': 5, ' ': 8},  # 3. 'digit' after 'dot'
            {'d': 3},  # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            {'s': 6, 'd': 7},  # 5. 'e'
            {'d': 7},  # 6. 'sign' after 'e'
            {'d': 7, ' ': 8},  # 7. 'digit' after 'e'
            {' ': 8}  # 8. end with 'blank'
        ]
        p = 0  # start with state 0
        for c in s:
            if '0' <= c <= '9':
                t = 'd'  # digit
            elif c in "+-":
                t = 's'  # sign
            elif c in "eE":
                t = 'e'  # e or E
            elif c in ". ":
                t = c  # dot, blank
            else:
                t = '?'  # unknown
            if t not in states[p]: return False
            p = states[p][t]
        return p in (2, 3, 7, 8)
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:#剑指 Offer 22. 链表中倒数第k个节点
        if k == 0:
            return None
        n = 0
        temp = head
        while temp:
            n+=1
            temp = temp.next
        while n - k > 0:
            head = head.next
            n-=1
        return head
    def reverseList(self, head: ListNode) -> ListNode:#剑指 Offer 24. 反转链表
        if head == None or head.next == None:
            return head
        p = head
        q = None
        while head:
            temp = head.next
            head.next = q
            q = head
            head = temp
        return  q  #双指针头插法
    def threeSum(self, nums):#15. 三数之和
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if nums[i] > 0:
                return res
            if i>0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums)-1
            while l < r:
                left, right = nums[l], nums[r]
                if nums[i] + left + right == 0:
                    res.append([nums[i], left, right])
                    while l < r and nums[l] == left:
                        l+=1
                    while l < r and nums[r] == right:
                        r-= 1
                elif nums[i] + left + right < 0:
                    while l < r and nums[l] == left:
                        l+=1
                else:
                    while l < r and nums[r] == right:
                        r-=1
        return res
    def fourSum(self, nums: [int], target: int) -> [[int]]:#18. 四数之和
        def three(nums, start, first, target):
            res = []
            for i in range(start, len(nums) - 2):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                l, r = i + 1, len(nums) - 1
                while l < r:
                    left, right = nums[l], nums[r]
                    if nums[i] + left + right == target-first:
                        res.append([first,nums[i], left, right])
                        while l < r and nums[l] == left:
                            l += 1
                        while l < r and nums[r] == right:
                            r -= 1
                    elif nums[i] + left + right < target-first:
                        while l < r and nums[l] == left:
                            l += 1
                    else:
                        while l < r and nums[r] == right:
                            r -= 1
            return res
        if len(nums) < 4:
            return []
        nums.sort()
        res = []
        for j in range(len(nums)-3):
            if j > 0 and nums[j] == nums[j-1]:
                continue
            touple = three(nums, j+1, nums[j], target)
            if three(nums, j+1, nums[j], target) != []:
                for i in touple:
                    res.append(i)
        return res



x = [1,-2,-5,-4,-3,3,3,5]
s = "5e3"
l =  [1,2,3,4,5]
head = create_linked_list(l)
m = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
solve = Solution()
r = solve.fourSum(x, -11)
print(r)
